package _02_并查集;

import _02_并查集.tools.Times;

public class Main {
    private static final int count = 1000000;
    public static void main(String[] args) {
        //testTime(new QuickFind(count));
        //testTime(new QuickUnion(count));
        testTime(new QuickUnion_Size(count));
        testTime(new QuickUnion_Rank(count));
        testTime(new QuickUnion_Rank_Pc(count));
        testTime(new QuickUnion_Rank_PS(count));
        testTime(new QuickUnion_Rank_PH(count));


    }

    static void testTime(UnionFind uf){
        Times.test(uf.getClass().getSimpleName(),()->{
            for(int i=0;i<count;++i){
                uf.union((int)(Math.random()*count),(int)(Math.random()*count));
            }
            for(int i=0;i<count;++i){
                uf.isSame((int)(Math.random()*count),(int)(Math.random()*count));
            }
        });

    }
    static void testQuickFind(){
        UnionFind uf = new QuickFind(12);
        uf.union(0,1);
        uf.union(0,3);
        uf.union(0,4);
        uf.union(2,3);
        uf.union(2,5);

        uf.union(6,7);

        uf.union(8,10);
        uf.union(9,10);
        uf.union(9,11);

        System.out.println(uf.isSame(4,7)); //false
        System.out.println(uf.isSame(6,7)); //true
        System.out.println(uf.isSame(8,11)); //true
        System.out.println(uf.isSame(1,5)); //true

        uf.union(4,7);
        System.out.println(uf.isSame(0,7)); //true
    }
}
